package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 12/9/20 11:34 AM
 *
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
 */
public class _123_买卖股票的最佳时机_III {

    public int maxProfit(int[] prices) {

        if (prices == null || prices.length <= 1) {

            return 0;
        }

        int[] leftToRs = new int[prices.length];
        int[] rightToLs = new int[prices.length];

        int leftMin = prices[0];
        for (int i = 1; i < prices.length; i++) {

            if (prices[i] < leftMin) {
                leftMin = prices[i];
            }

            if (leftToRs[i - 1] < prices[i] - leftMin) {

                leftToRs[i] = prices[i] - leftMin;
            }else {
                leftToRs[i] = leftToRs[i-1];
            }
        }

        int rightMax = prices[prices.length - 1];
        for (int i = prices.length - 2; i >= 0 ; i--) {

            if (prices[i] > rightMax) {

                rightMax = prices[i];
            }


            if (rightMax - prices[i] > rightToLs[i + 1]) {

                rightToLs[i] = rightMax - prices[i];
            }else {

                rightToLs[i] = rightToLs[i + 1];
            }

        }

        int max = rightToLs[0];
        for (int i = 0; i < prices.length - 1; i++) {

            int maxV = leftToRs[i] + rightToLs[i + 1];

            if (max < maxV) {

                max = maxV;
            }

        }

        return max;
    }
}
